import Data.List (elemIndices, (\\), sortOn)

type Coord = (Int, Int)

cab :: (Coord, Coord) -> Int
cab ((x1, y1), (x2, y2)) = abs (x1 - x2) + abs (y1 - y2)

pairs :: Eq a => [a] -> [(a, a)]
pairs xs = [(x1, x2) | x1 <- xs, x2 <- xs]

lines2coords :: [String] -> [Coord]
lines2coords = 
    go 0
    where
        go _ [] = []
        go i (l:ls) = (map (\c -> (i, c)) (elemIndices '#' l)) ++ go (i + 1) ls

expandN :: Int -> [Coord] -> [Coord]
expandN n = 
    transpose . expandRowsN n . transpose . expandRowsN n
    where 
        transpose = sortOn fst . map (\(x, y) -> (y, x))

expandRowsN :: Int -> [Coord] -> [Coord]
expandRowsN n = 
    go 0 0 
    where
        go _ _ [] = []
        go idx offset coords = 
            if null currentLine then
                go (idx + 1) (offset + 1) coords
            else
                currentLine' ++ go (idx + 1) offset coords'
            where
                currentLine  = filter ((== idx) . fst) coords
                currentLine' = map (\(x, y) -> (x + offset, y)) currentLine
                coords'      = coords \\ currentLine 

main = do
    contents <- readFile "input.txt"
    let coords = lines2coords . lines $ contents

    print $ (`div` 2) . sum . map cab . pairs . expandN 1 $ coords
    print $ (`div` 2) . sum . map cab . pairs . expandN (1000000 - 1) $ coords
